package _02_并查集;
/*
    方案:Quick_Union ->基于size的优化:元素少的树嫁接到元素多的树
 */
public class QuickUnion_Size extends QuickUnion{
    private int[] sizes; //存放每棵树的节点个数
    public QuickUnion_Size(int capacity) {
        super(capacity);
        sizes = new int[capacity];
        for (int i = 0; i < sizes.length; i++) {
            sizes[i] = 1; //初始化时，每棵树的节点个数都为1
        }
    }

    /*
        将v1的根节点嫁接到v2的根节点上
     */
    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1); //v1的根节点
        int p2 = find(v2); // v2的根节点

        if(p1 == p2) return;

        if(sizes[p1]<sizes[p2]){ //p1的节点个数小于p2的节点个数
            parents[p1] = p2; //将p1根节点嫁接到p2上
            sizes[p2] += sizes[p1]; //更新树的节点个数
        }else{
            parents[p2] = p1;
            sizes[p1] += sizes[p2];
        }
    }
}
